package dp;

import java.util.Arrays;

public class leetcode983 {
    static int[] t={1,7,30};

    /**
     * 递归朴素做法
     * @param days
     * @param costs
     * @return
     */
    public int mincostTickets1(int[] days, int[] costs) {
//从第day[i]开始的最低票价为做出某种决策后的第j天的最低票价加上当前决策的钱
        return  dg1(days,costs,0);
    }
    static int dg1(int[]days,int[]costs,int i){
        if(i==days.length)return 0;//到达末尾了
        int res=Integer.MAX_VALUE;
        for(int k=0,j=i;k<=2;k++){//k表示方案,j表示天数下标
//当我们选择一种选择后，我们要获取下次对应开始天数下标
            //停止条件 days[j]>i+t[k]
            while(j< days.length&&days[j]<days[i]+t[k])j++;
            res=Math.min(res,costs[k]+dg1(days,costs,j));
        }
        return res;
    }

    /**
     * 加上记忆化搜索
     * @param days
     * @param costs
     * @return
     */
    public int mincostTickets2(int[] days, int[] costs) {
//从第day[i]开始的最低票价为做出某种决策后的第j天的最低票价加上当前决策的钱
        int length=days.length;
        int[] dp=new int[length];
        Arrays.fill(dp,Integer.MAX_VALUE);
        return  dg2(days,costs,dp,0);
    }
    static int dg2(int[]days,int[]costs,int[] dp,int i){
        if(i==days.length)return 0;//到达末尾了
        if(dp[i]!=Integer.MAX_VALUE)return dp[i];
        for(int k=0,j=i;k<=2;k++){//k表示方案,j表示天数下标
//当我们选择一种选择后，我们要获取下次对应开始天数下标
            //停止条件 days[j]>i+t[k]
            while(j< days.length&&days[j]<days[i]+t[k])j++;
            dp[i]=Math.min(dp[i],costs[k]+dg2(days,costs,dp,j));
        }
        return dp[i];
    }

    //dp做法
    public int mincostTickets(int[] days, int[] costs) {
//从第day[i]开始的最低票价为做出某种决策后的第j天的最低票价加上当前决策的钱
        int length=days.length;
        int[] dp=new int[length+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[length]=0;
        for(int i=days.length-1;i>=0;i--){
            //对于从第i天开始的最小值,等于三种方案中合理方案的较小值
            for(int k=0,j=i;k<3;k++){
                while(j< days.length&&days[j]<days[i]+t[k])j++;
                dp[i]=Math.min(dp[i],costs[k]+dp[j]);
            }
        }
        return dp[0];
    }
}
